package com.jia.leetCode;

import javafx.util.Pair;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-16 13:28
 */
public class Pro5490 {
    Queue<Pair<Integer, Integer>> queue;
    Set<Integer> visited;
    public Pro5490() {
        queue = new LinkedList<>();
        visited = new HashSet<>();
    }

    public int minDays(int n) {
        queue.offer(new Pair(n, 0));
        visited.add(n);
        while (!queue.isEmpty()) {
            int ans = bfs();
            if (ans > -1) {
                return ans;
            }
        }
        return -1;
    }

    private int bfs() {
        Pair<Integer, Integer> pair = queue.poll();
        int num = pair.getKey();
        int day = pair.getValue();
        if (num == 0) {
            return day;
        }
        int next1 = num - 1;
        queueOffer(next1, day);

        if ((num & 1) == 0) {
            int next2 = num / 2;
            queueOffer(next2, day);

        }

        if (num % 3 == 0) {
            int next3 = num - ((num / 3) << 1);
            queueOffer(next3, day);
        }
        return -1;
    }

    private void queueOffer(int next, int day) {
        if (!visited.contains(next)) {
            visited.add(next);
            queue.offer(new Pair(next, day + 1));
        }
    }
    //超内存
    public int minDays2(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            if(i % 2 == 0 && i % 3 == 0) {
                dp[i] = Math.min(dp[i / 2], dp[i - 2 * (i / 3)]) + 1; //%2 %3
                dp[i] = Math.min(dp[i - 1] + 1, dp[i]);  //吃一个
            }else if(i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2], dp[i - 1]) + 1;
            }else if(i % 3 == 0) {
                dp[i] = Math.min(dp[i - 2 * (i / 3)], dp[i-1]) + 1;
            }else {
                dp[i] = dp[i-1] + 1;
            }
        }
        //System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}
